package com.feishi.project.test;

import java.awt.*;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: caixq
 * Date: 2019-08-08
 * Time: 上午11:44
 */
public class ASearch {
    public static void main(String[] args) throws InterruptedException {
        Panel panel = new Panel(660, 660);
//        panel.drawLine(30,30,30,30,600,600);
        int x = 50;
        int y = 50;
        //画棋盘
        Label[][] labels = panel.addChessboard(x, y);
        /**
         * 添加障碍物
         * */
        setObstacle(labels, 1, 0.4f);
        panel.setVisible(true);

        Label startLabel = labels[0][(int) ((y - 1) * Math.random())];
        Label endLabel = labels[x - 1][(int) ((y - 1) * Math.random())];

        startLabel.setBackground(Color.BLUE);
        endLabel.setBackground(Color.BLUE);

        Point a = findWayA(labels, startLabel, endLabel);
        Point b = findWayB(labels, startLabel, endLabel);


        //打印终点得到的最终探索路径
        Point p = a;
        p.setColor(labels, Color.magenta);
        p = p.parent;
        while (p.parent != null) {
            p.setColor(labels, Color.magenta);
            p = p.parent;
        }
        //打印终点得到的最终探索路径
        p = b;
//        p.setColor(labels,Color.magenta);
        p = p.parent;
        while (p.parent != null) {
            p.setColor(labels, Color.CYAN);
            p = p.parent;
        }


    }

    private static Point findWayB(Label[][] labels, Label startLabel, Label endLabel) {
        int x = labels.length;
        int y = labels[0].length;
        /**
         * 映射棋盘与坐标
         * */
        Map<Label, Point> map = new HashMap<>();
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                map.put(labels[i][j], new Point(i, j));
            }
        }
        /**
         * 在第一行和最后一行随机生成起点和终点
         * */
        Point start = map.get(startLabel);
        Point end = map.get(endLabel);
        Point t = start;
        while (t != end) {
            //探索起点设为不可探索
            t.closed = true;
            //以最新点为起点循环探索
//                if(t!=start)t.setColor(labels,Color.CYAN);
            t = find(labels, t, end, map);
//            Thread.sleep(10);
//            if(t!=start)t.setColor(labels,Color.WHITE);

        }
        return t;
    }

    private static Point findWayA(Label[][] labels, Label startLabel, Label endLabel) {
        int x = labels.length;
        int y = labels[0].length;
        /**
         * 映射棋盘与坐标
         * */
        Map<Label, Point> map = new HashMap<>();
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                map.put(labels[i][j], new Point(i, j));
            }
        }
        /**
         * 在第一行和最后一行随机生成起点和终点
         * */
        Point start = map.get(startLabel);
        Point end = map.get(endLabel);
        HashSet<Point> out = new HashSet<>();
        out.add(start);//以起点为基准开始探索
        while (out.size() > 0) {
            //探索起点设为不可探索
            HashSet<Point> out1 = new HashSet<>();
            for (Point point : out) {
                point.closed = true;
            }
            //以最新点为起点循环探索
            for (Point from : out) {
                if (from == end) continue;
//                if(from!=start)from.setColor(labels,Color.CYAN);
                find(labels, from, end, map, out1);
//                if(from!=start)from.setColor(labels,Color.WHITE);
            }
            //探索到的新目标作为新的起点
            out = out1;
//            Thread.sleep(10);
        }
        return end;
    }

    /**
     * @Params labels : 坐标点二维数组
     * @Param start : 起点
     * @Param end : 终点
     * @Param map : 坐标点映射
     * @Param out : 最新探索点输出
     */
    private static Point find(Label[][] labels, Point start, Point end, Map<Label, Point> map) {
        Set<Point> target = new HashSet<>();

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                /**
                 * 避开越界
                 * */
                if (start.x + i < 0 || start.x + i >= labels.length) {
                    continue;
                }
                if (start.y + j < 0 || start.y + j >= labels[0].length) {
                    continue;
                }

                int x = start.x + i;
                int y = start.y + j;
                Label label = labels[x][y];
                Point point = map.get(labels[x][y]);

//                System.out.println(point.x+":"+point.y+":"+point.getH(end)+":"+end.x+":"+end.y);
//                if(point.getH(end)==0){
//                    System.out.println(142);
//                }
                //探索目标已封闭或者是障碍物,跳过
                if (point.closed || labels[x][y].getBackground() == Color.BLACK) {
                    continue;
                }
                int g = i * j == 0 ? 10 : 14;
                //已探索目标切当前路径相对距离更远,放弃
                if (point.parent != null && point.getG(g, start) > point.g) {
                    target.add(point);
                    continue;
                }
                point.parent = start;
                point.h = point.getH(end);
                if (point.getH(end) != 0) label.setBackground(Color.DARK_GRAY);
                point.g = point.getG(g, start);
                //设置当前点距离权值
                label.setText(String.valueOf(point.h + point.g));
                target.add(point);
            }
        }
        if (start.parent == null)
            System.out.println(111);
        start.closed = true;
        if (target.size() == 0) {
            return start.parent;
        }
        Point o = null;
        for (Point point : target) {
            if (o == null) o = point;
            o = o.h > point.h ? point : o;
        }
        return o;
    }

    /**
     * @Params labels : 坐标点二维数组
     * @Param start : 起点
     * @Param end : 终点
     * @Param map : 坐标点映射
     * @Param out : 最新探索点输出
     */
    private static void find(Label[][] labels, Point start, Point end, Map<Label, Point> map, HashSet<Point> out) {

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                /**
                 * 避开越界
                 * */
                if (start.x + i < 0 || start.x + i >= labels.length) {
                    continue;
                }
                if (start.y + j < 0 || start.y + j >= labels[0].length) {
                    continue;
                }

                int x = start.x + i;
                int y = start.y + j;
                Label label = labels[x][y];
                Point point = map.get(labels[x][y]);

//                System.out.println(point.x+":"+point.y+":"+point.getH(end)+":"+end.x+":"+end.y);
//                if(point.getH(end)==0){
//                    System.out.println(142);
//                }
                //探索目标已封闭或者是障碍物,跳过
                if (point.closed || labels[x][y].getBackground() == Color.BLACK) {
                    continue;
                }
                int g = i * j == 0 ? 10 : 14;
                //已探索目标切当前路径相对距离更远,放弃
                if (point.parent != null && point.getG(g, start) > point.g) {
                    continue;
                }
                point.parent = start;
                point.h = point.getH(end);
//                if(point.getH(end)!=0)label.setBackground(Color.DARK_GRAY);
                point.g = point.getG(g, start);
                //设置当前点距离权值
                //label.setText(String.valueOf(point.h+point.g));
                out.add(point);
            }
        }
    }


    static class Point {
        int x;
        int y;
        int g;
        int h;
        int status;
        Point parent;
        boolean closed;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void setColor(Label[][] labels, Color color) {
            labels[x][y].setBackground(color);
        }

        public int getG(int g, Point p) {
            return p.g + g;
        }

        public int getH(Point end) {
            return 10 * (Math.abs(x - end.x) + Math.abs(y - end.y));
        }

        public boolean far(Point point) {
            return g + h - point.g - point.h > 0;
        }
    }

    private static void setObstacle(Label[][] labels, int borderSize, float proportion) {
        for (int i = borderSize; i < labels.length - borderSize; i++) {
            for (int j = borderSize; j < labels[i].length - borderSize; j++) {
                if (proportion > Math.random()) {
                    labels[i][j].setBackground(Color.BLACK);
                }
            }
        }
    }
}
